4848. Быстрая сортировка

 

Отсортируйте заданную последовательность чисел в неубывающем порядке.

 

Вход. В одной строке содержится последовательность, содержащая не более 105 целых чисел.

 

Выход. В одной строке вывести последовательность чисел в неубывающем порядке.

 

Пример входа

Пример выхода

4 1 4 8 6 6 5

1 4 4 5 6 6 8

 

 

РЕШЕНИЕ

сортировка

 

Анализ алгоритма

Прочитайте последовательность чисел в массив до конца файла и реализуйте любой алгоритм сортировки.

 

Реализация алгоритма

Рассмотрим реализацию при помощи STL.

 

#include <cstdio>

#include <algorithm>

#define MAX 100001

using namespace std;

 

int i, n;

int m[MAX];

 

int main(void)

{

  n = 0;

  while(scanf("%d",&m[n]) == 1) n++;

 

  sort(m,m+n);

 

  for(i = 0; i < n; i++)

    printf("%d ",m[i]);

  printf("\n");

 

  return 0;

}

 

Реализация алгоритма – обменная сортировка

Решение дает TLE, так как сложность алгоритма O(n2).

 

#include <stdio.h>

#include <string.h>

#define MAX 100001

 

int m[MAX];

int n, i, j;

 

void SwapSort(int *m)

{

  int i, j, temp;

  for(i = 0; i < n; i++)

  for(j = i + 1; j < n; j++)

    if (m[i] > m[j]) temp = m[i], m[i] = m[j], m[j] = temp;

}

 

int main(void)

{

  n = 0;

  while(scanf("%d",&m[n]) == 1) n++;

 

  SwapSort(m);

 

  printf("%d",m[0]);

  for(i = 1; i < n; i++)

    printf(" %d",m[i]);

  printf("\n");

 

  return 0;

}

 

Реализация алгоритма – быстрая сортировка

Решение дает TLE, так как сложность алгоритма в худшем случае O(n2). В качестве опорного элемента выбираетя самый левый.

 

#include <stdio.h>

#define MAX 100001

 

int m[MAX];

int i, n;

 

void swap(int &i, int &j)

{

  int temp = i; i = j; j = temp;

}

 

int Partition(int L, int R)

{

  int x = m[L], i = L - 1, j = R + 1;

  while(1)

  {

    do j--; while (m[j] > x);

    do i++; while (m[i] < x);

    if (i < j) swap(m[i],m[j]); else return j;

  }

}

 

void QuickSort(int L, int R)

{

  int q;

  if (L < R)

  {

    q = Partition(L, R);

    QuickSort(L,q); QuickSort(q+1,R);

  }

}

 

int main(void)

{

  n = 0;

  while(scanf("%d",&m[n]) == 1) n++;

 

  QuickSort(0,n-1);

 

  printf("%d",m[0]);

  for(i = 1; i < n; i++)

    printf(" %d",m[i]);

  printf("\n");

 

  return 0;

}

 

Реализация алгоритма – быстрая сортировка (опорный элемент – медиана трех)

 

#include <stdio.h>

#define MAX 100001

 

int m[MAX];

int i, n;

 

int min(int i, int j)

{

  return (i < j) ? i : j;

}

 

int max(int i, int j)

{

  return (i > j) ? i : j;

}

 

void swap(int &i, int &j)

{

  int temp = i; i = j; j = temp;

}

 

int Partition(int L, int R)

{

  int x, i = L - 1, j = R + 1;

 

  // pivot = median of three

  int a = m[L], b = m[(L+R)/2], c = m[R];

  x = a + b + c - min(min(a,b),c) - max(max(a,b),c);

 

  while(1)

  {

    do j--; while (m[j] > x);

    do i++; while (m[i] < x);

    if (i < j) swap(m[i],m[j]); else return j;

  }

}

 

void QuickSort(int L, int R)

{

  int q;

  if (L < R)

  {

    q = Partition(L, R);

    QuickSort(L,q); QuickSort(q+1,R);

  }

}

 

int main(void)

{

  //freopen("4848.in","r",stdin);

  n = 0;

  while(scanf("%d",&m[n]) == 1) n++;

  QuickSort(0,n-1);

  printf("%d",m[0]);

  for(i = 1; i < n; i++)

    printf(" %d",m[i]);

  printf("\n");

  return 0;

}

 

Реализация алгоритма – быстрая сортировка (опорный элемент – медиана трех) – версия 2

 

#include <stdio.h>

#include <string.h>

#define MAX 100001

 

int m[MAX];

int n, i, j;

 

int min(int i, int j)

{

  return (i < j) ? i : j;

}

 

int max(int i, int j)

{

  return (i > j) ? i : j;

}

 

void swap(int &i, int &j)

{

  int temp = i; i = j; j = temp;

}

 

int Partition(int L, int R)

{

  int x, i = L, j = R;

 

  // pivot = median of three

  int a = m[L], b = m[(L+R)/2], c = m[R];

  x = a + b + c - min(min(a,b),c) - max(max(a,b),c);

 

  while (i <= j)

  {

    while (m[i] < x) i++;

    while (m[j] > x) j--;

    if (i <= j)

      swap(m[i++],m[j--]);

  }

  return i;

}

 

void QuickSort(int L, int R)

{

  int q;

  if (L < R)

  {

    q = Partition(L, R);

    if (L < q - 1) QuickSort(L,q-1);

    if (q < R) QuickSort(q,R);

  }

}

 

int main(void)

{

  n = 0;

  while(scanf("%d",&m[n]) == 1) n++;

  QuickSort(0,n-1);

  printf("%d",m[0]);

  for(i = 1; i < n; i++)

    printf(" %d",m[i]);

  printf("\n");

  return 0;

}

 

Реализация алгоритма – сорировка слиянием

 

#include <stdio.h>

#include <string.h>

#define MAX 100001

 

int m[MAX];

int n, i, j;

 

void merge(int *a, int bleft, int bright, int cleft, int cright)

{

  // a[bleft..bright] and a[cleft..cright] are merged into a,

  // bright < cleft

  int i, left = bleft, len = cright - bleft + 1;

  int *res = new int[len];

  for(i = 0; i < len; i++)

  {

    if ((bleft > bright) || (cleft > cright)) break;

    if (a[bleft] <= a[cleft]) res[i] = a[bleft++];

    else res[i] = a[cleft++];

  }

  while (bleft <= bright) res[i++] = a[bleft++];

  while (cleft <= cright) res[i++] = a[cleft++];

  memcpy(a + left,res,len*sizeof(int));

  delete[] res;

}

 

void mergeSort(int *a, int left, int right)

{ 

  if (left >= right) return;

  int middle = (left + right) / 2;

  mergeSort(a,left,middle);

  mergeSort(a,middle+1,right);

  merge(a, left, middle, middle + 1, right);

}

 

int main(void)

{

  n = 0;

  while(scanf("%d",&m[n]) == 1) n++;

 

  mergeSort(m, 0, n - 1);

 

  printf("%d",m[0]);

  for(i = 1; i < n; i++)

    printf(" %d",m[i]);

  printf("\n");

 

  return 0;

}

 

Реализация алгоритма – сортировка слиянием (оптимизированная)

 

#include <stdio.h>

#include <string.h>

#define MAX 100001

 

int m[MAX];

int n, i, j;

 

void merge(int *a, int bleft, int bright, int cleft, int cright)

{

  // a[bleft..bright] -> res[]

  // res[0..len-1] a[cleft..cright] are merged into a[bleft..cright]

  // we copy only half of array

  int i, len = bright - bleft + 1, resCur = 0;

  int *res = new int[len];

  memcpy(res,a + bleft,len*sizeof(int));

  while((resCur < len) && (cleft <= cright))

  {

    if (res[resCur] <= a[cleft]) a[bleft++] = res[resCur++];

    else a[bleft++] = a[cleft++];

  }

  while (resCur < len) a[bleft++] = res[resCur++];

  delete[] res;

}

 

void mergeSort(int *a, int left, int right)

{ 

  if (left >= right) return;

  int middle = (left + right) / 2;

  mergeSort(a,left,middle);

  mergeSort(a,middle+1,right);

  merge(a, left, middle, middle + 1, right);

}

 

int main(void)

{

  n = 0;

  while(scanf("%d",&m[n]) == 1) n++;

 

  mergeSort(m, 0, n - 1);

 

  printf("%d",m[0]);

  for(i = 1; i < n; i++)

    printf(" %d",m[i]);

  printf("\n");

 

  return 0;

}

 

Java реализация – ArrayList Sort

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    ArrayList<Integer> a = new ArrayList<Integer>();

    while(con.hasNext())

    {

      int val = con.nextInt();

      a.add(val);

    }

   

    Collections.sort(a);

  

    for(int i = 0; i < a.size(); i++)

      System.out.print(a.get(i) + " ");

    System.out.println();

    con.close();

  }

}

 

Java реализация – компаратор

 

import java.util.*;

 

class f implements Comparator<Integer>

{

  // a < b means a - b < 0

  public int compare(Integer a, Integer b)

  {

    return a - b;

  }

}

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    ArrayList<Integer> a = new ArrayList<Integer>();

    while(con.hasNext())

    {

      int val = con.nextInt();

      a.add(val);

    }

   

    Collections.sort(a, new f());

  

    for(int i = 0; i < a.size(); i++)

      System.out.print(a.get(i) + " ");

    System.out.println();

    con.close();

  }

}

 

Python реализация

 

lst = list(map(int,input().split()))

lst.sort()

print(*lst)